package OJ;

import java.util.*;

public class TestOJ {

    //https://leetcode.cn/problems/single-number/description/
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }

        for(int i=0;i<nums.length;i++){
            if(!set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

    //https://leetcode.cn/problems/copy-list-with-random-pointer/
    /*
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map=new HashMap<>();
        // 1. 第一次遍历链表
        Node cur=head;
        while(cur!=null) {
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }//map中构建好了节点之间的映射关系

        // 2. 再次遍历链表
        cur=head;
        while(cur!=null) {
            map.get(cur).next=map.get(cur.next);//新节点的next值=旧节点next节点(key)对应的value值
            map.get(cur).random=map.get(cur.random);//新节点的random值=旧节点random节点(key)对应的value值
            cur=cur.next;
        }
        return map.get(head);//新链表的head就是旧链表的head对应的value
    }

     */

    //https://leetcode.cn/problems/jewels-and-stones/
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set=new HashSet<>();
        int count=0;
        //遍历宝石,拿到一个个字符
        for(int i=0;i<jewels.length();i++) {
            char ch=jewels.charAt(i);
            set.add(ch);
        }
        for(int i=0;i<stones.length();i++) {
            char ch=stones.charAt(i);
            if(set.contains(ch)) {
                count++;
            }
        }
        return count;
    }

    //https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
    /*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1, str2);
        }
    }
    public static void func(String str1, String str2) {
        HashSet<Character> set1 = new HashSet<>();
        HashSet<Character> set2 = new HashSet<>();
        for (char ch :
                str2.toUpperCase().toCharArray()) { //将str2变成大写变成字符数组
            set1.add(ch);
        }
        for (char ch :
                str1.toUpperCase().toCharArray()) { //将str1变成大写变成字符数组
            if (!set1.contains(ch) && !set2.contains(ch)) {
                System.out.print(ch);
                set2.add(ch);
            }
        }
    }

     */

    //https://leetcode.cn/problems/top-k-frequent-words/
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计每个单词出现的次数
        HashMap<String ,Integer> map=new HashMap<>();
        for(String word:words){
            if(map.get(word)==null){
                //之前没有存放过
                map.put(word,1);
            }else {
                int val=map.get(word);
                map.put(word,val+1);
            }
        }
        // 2. 现已经得到了每个单词的出现次数,存进了map中,接下来遍历map查看单词的出现次数
        //将单词出现频率存放到小根堆中,以TOPK问题解决
        //2.1 创建小根堆,并定义entry进行比较的逻辑,按照单词出现频率进行比较,当频率
        PriorityQueue<Map.Entry<String ,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>() {
            @Override
            public int compare(Map.Entry<String,Integer> o1, Map.Entry<String,Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());//字典序相同时,按照key的字典序建大根堆
                }
                return o1.getValue()-o2.getValue();//字典序不同时,按照频率建小根堆
            }
        });
        for(Map.Entry<String,Integer> entry:map.entrySet()) {
            if(minHeap.size()<k) {
                //建堆
                minHeap.offer(entry);
            }else {
                //建堆完成,后面的元素需要和堆顶元素进行比较
                Map.Entry<String,Integer> top=minHeap.peek();
                if(top.getValue().compareTo(entry.getValue())==0){//频率相同,比较字典序
                    if(top.getKey().compareTo(entry.getKey())>0) {
                        //出堆顶,入新元素
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {//频率不相同
                    if(entry.getValue().compareTo(top.getValue())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        List<String> list=new ArrayList<>();
        for(int i=0;i<k;i++) {
            Map.Entry<String,Integer> tmp=minHeap.poll();
            list.add(tmp.getKey());
        }
        Collections.reverse(list);//逆置
        return list;
    }


    public static void main(String[] args) {
        int[] array={1,3,2,3,4,6,7,4,5,6,9,8,9};
        HashSet<Integer> set=new HashSet<>();
        //找出十万个数据中第一个重复的值
        /*
        for(int x:array) {
            if(!set.contains(x)) {
                set.add(x);
            }else {
                System.out.println(x);
                return;
            }
        }

         */
        //给你十万个数据,把这些数据去重

        /*
        //统计十万个数据当中,重复数据的出现次数
        必须使用map
         */

        Map<Integer,Integer> map=new HashMap<>();//key是数组元素的值,value是对应出现次数
        for(int i=0;i<array.length;i++) {
            if(map.get(array[i])==null) {
                //当前map没有存储过这个值
                map.put(array[i],1);

            }else {
                int val=map.get(array[i]);
                map.put(array[i],val+1);
            }
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
            System.out.println("数字:"+entry.getKey()+",次数:"+entry.getValue());
        }
    }







}
